背包动态规划复习

01背包

考虑到最多只能选取1个，反向枚举顺序满足当前决策不会影响到同一个物品的其他决策。

朴素枚举 $\text{O}(nv)$

for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--){
	dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
}

洛谷-P1048 采药

##P4163 [SCOI2007]排列

本着来写状压的，奈何发现手算一波复杂度后感觉不对。

那么我们考虑搜索（$n\leq10$），暴力搞的话复杂度为 $\text{O}(n!\times T)$，无法通过。

那么我们考虑使用一点点的状压思想和搜索技巧：

2020.09.02-2020.09.05 学习日志

高二开始了。

数据结构专练

耗时一个暑假的成果，还算是稍有成绩。

博弈论杂题

博弈论？有点玄学的东西。

做到博弈论题目的时候，我们虽然可以巧妙的利用几个小套路，但是大部分时候还是依赖选手的耐心和手玩能力。

以下仅给出题目链接和部分思路，不给出一句话题意和详细代码，请读者选择阅读。

2020-07-08 自测赛总结

第一次自评，就被神仙 $\text{Sunward}$ 包菜了/kk

晚自习考的，大概总用时 $3\text h$ 多一点点吧。

二阶常系数齐次线性递推

题意

给定一个序列的线性递推式：

$f_n= \begin{cases} a\cdot f_{n-1}+b\cdot f_{n-2}&, & n\geq2 \\ f_1 & , & n=1 \\ f_0 & , & n=0 \end{cases}$

多组询问，给定 $n,a,b,f_0,f_1$，求 $f_n$ 的值。

二次剩余

定义

存在正整数 $a$ 满足 ${a}^2\equiv n\pmod{p}$ 的正整数 $n$ 是在模 $p$ 的意义下的二次剩余，其中 $p$ 为奇质数。

单调队列优化DP

​ \%Sunward\text{_}z，神仙在线教会蒟蒻单调队列优化 $dp$。

思想

​ 考虑到做动规的题目时会经常遇到形如这样的转移方程：

$dp_{i,j}=\max(dp_{i-1,j}+a_j)_{(l\leq j\leq r)}+b_i$

随手录1

​ 请注意每个例子的第一行即为问题要求。

​ 如果您觉得我的推导存在问题，那么请评论或私信我。

​ 可能会附上题目位置。